package binary_tree

//输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
//
//例如：
//
//给定二叉树 [3,9,20,null,null,15,7]，返回最大深度为3

func MaxDepth(root *TreeNode) int {
	if root == nil {
		return 0
	}
	return max(MaxDepth(root.left), MaxDepth(root.right)) + 1
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func MaxDepthOfBFS(root *TreeNode) int {
	// 边界
	if root == nil {
		return 0
	}
	depth := 0
	var queue []*TreeNode
	queue = append(queue, root)
	// bfs
	for len(queue) > 0 {
		length := len(queue)
		for i := 0; i < length; i++ {
			cur := queue[0]
			queue = queue[1:]
			if cur.left != nil {
				queue = append(queue, cur.left)
			}
			if cur.right != nil {
				queue = append(queue, cur.right)
			}
		}
		depth += 1
	}
	return depth
}
